package me.mingshan.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author hanjuntao
 * @date 2025/8/28 0028
 */
public class BinaryTreeExtend {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        //       1
        //      2  3
        //    4   5
        System.out.println(binaryTreePaths2(root));
    }


    /**
     * 二叉树的所有路径
     *
     * 使用字符串拼接（字符串值传递）
     *
     * @param root
     * @return
     */
    public static List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root != null) {
            // 因为递归调用左子节点时，s 的修改在递归返回后不会影响当前作用域的 s，
            // 但注意：在 Java 中，字符串是不可变的，每次修改都会创建新字符串，因此递归调用中传递的是新字符串，不会影响父调用的 s
            dfs(root, "", result);
        }
        return result;
    }

    private static void dfs(TreeNode node, String path, List<String> result) {
        if (node == null) {
            return;
        }

        // 构建当前路径
        if (path.isEmpty()) {
            path = String.valueOf(node.val);
        } else {
            path += "->" + node.val;
        }

        // 如果是叶子节点，添加路径到结果
        if (node.left == null && node.right == null) {
            result.add(path);
            return;
        }

        // 递归遍历左右子树
        dfs(node.left, path, result);
        dfs(node.right, path, result);
    }

    /**
     * 二叉树的所有路径
     *
     * 使用可变对象，需要特别注意回溯处理，因为 List 是引用传递，所有递归调用共享同一个 List 对象
     *
     * 所以需要回溯到上一级，将当前节点从路径中删除, 这样回溯到递归起始节点时，路径中的节点已经全部被删除，所以结果中不会出现重复路径
     *
     * @param root
     * @return
     */
    public static List<String> binaryTreePaths2(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<String> result = new ArrayList<>();
        // 使用 List 存储路径
        List<Character> path = new ArrayList<>();

        dfsWithList(root, path, result);

        return result;
    }

    private static void dfsWithList(TreeNode root, List<Character> path, List<String> result) {
        if (root == null) {
            return;
        }

        // 添加当前节点值到路径
        path.add((char) ('0' + root.val));

        if (root.left == null && root.right == null) {
            // 构建路径字符串
            StringBuilder sb = new StringBuilder();
            for (char c : path) {
                sb.append(c);
            }
            String pathStr = sb.toString();
            System.out.println(pathStr);
            result.add(pathStr);

            // 回溯：移除当前节点
            path.remove(path.size() - 1);
            return;
        }

        // 递归处理左右子树
        dfsWithList(root.left, path, result);
        dfsWithList(root.right, path, result);

        // 回溯：移除当前节点
        path.remove(path.size() - 1);
    }



    /**
     * 124
     * 5
     * 3
     *
     * @param root
     * @return
     */
    private static void dfsWithListERROR(TreeNode root, List<Character> path, List<String> result) {
        if (root == null) {
            return;
        }

        // 添加当前节点值到路径
        path.add((char) ('0' + root.val));

        if (root.left == null && root.right == null) {
            // 构建路径字符串
            StringBuilder sb = new StringBuilder();
            for (char c : path) {
                sb.append(c);
            }
            String pathStr = sb.toString();
            System.out.println(pathStr);
            result.add(pathStr);

            // 回溯：移除当前节点
            path.clear();
            return;
        }

        // 递归处理左右子树
        dfsWithListERROR(root.left, path, result);
        dfsWithListERROR(root.right, path, result);
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public void print() {
            System.out.println( val);
        }
    }

}
